Simulation of objects interacting in a space has become a vital tool for many areas of engineering and scientific investigation, as well as for single and multi-player game simulations. Scientists for example can use computer simulations to calculate and predict the motions and interactions of asteroids, comets, and other planetary bodies. Other scientific applications include such diverse areas as plasma physics, suspension flows, vortex simulations, porous media, and materials science.
In addition, simulation of objects interacting in space lies at the heart of many computer-enabled games, including so-called “Massively Multi-player Online Games” or “MMOG's.”
As scientists and engineers seek to analyze ever more complex problems, and as more and more gamers wish to participate simultaneously in MMOG's, many of these technical and gaming applications face the problem of how to provide larger and larger simulations, while maintaining the simulation speed (in some cases real-time) and also minimizing the cost of the engine. Also, there is frequently a problem of scalability. At some point after a given system has been designed and implemented, it is not uncommon for users to wish to expand the capabilities of the system, so as to accommodate more objects and users, and/or more complex simulations, than were originally anticipated.
There is also a rising demand, especially in gaming applications, for better and better graphics, and also for options to participate using devices other than conventional personal computers, for example by using a tablet, a smart phone, or some other hand-held device with limited processing capacity.
One approach to providing larger and faster simulations is to use a single, high-end, dedicated server with very high speed and capacity. However, these so-called “super-computers” can be prohibitively expensive, and they can be difficult to scale beyond certain manufacturer-specified limits.
Another approach, used for example in some online environments, is to distribute most or all of the computation among the personal computers that are used by gamers to access the game. However, for this approach the required data traffic between the nodes increases rapidly as the number of nodes increases, effectively setting an upper limit on the number of players that can be accommodated simultaneously. Also, the computing speeds of the player nodes may vary, such that slower nodes may reduce the speed of the simulation and/or introduce latency effects. In addition, this approach excludes access to the MMOG environment using smart phones, tablets, and other web access devices that have relatively low on-board computing power. And also, this type of architecture can consume significant amounts of computing resources on the user computers during a game, which can limit the ability of the user computers to perform other tasks simultaneously, such as rendering graphics in support of the game. Also, users are often separated from each other by large distances, so that the internet latencies resulting from this type of distributed computing can rise to unacceptable levels.
Yet another approach is to use a cluster of smaller computers, such as a “Beowulf” cluster, as the simulation engine. A Beowulf cluster is a cluster of typically identical, commodity-grade computers that are connected into a small local-area network, having libraries and programs installed which allow processing to be shared among them. The result can be a high-performance, parallel computing cluster assembled from inexpensive personal computer hardware.
Of course, for a cluster of commodity-grade computers to serve as a simulation engine, the computing load must be parallelized, so that it can be distributed among the nodes of the cluster. One approach is to assign specific types of tasks to each node. For example, one node might keep track of the identities and descriptive parameters associated with each object in the simulation, another node might keep track of positions and velocities of objects within the cluster, another node might control “artificial intelligence” or “AI” objects that are not under participant control, yet another node might be dedicated to computing the results of interactions between objects in the simulation, and so forth. However, this approach can result in highly unequal loads being placed on the nodes of the cluster, as well as requiring massive intercommunication between the nodes. Also, a system using this approach is not easily scaled.
Another approach is to assign separate regions or sectors of the simulated space to separate nodes, so that each node in the cluster provides a full, or nearly full, simulation of all activity within its assigned sector(s). However, it is not uncommon for the objects in a simulation to be unequally distributed throughout the simulated space, so that nothing is happening in many sectors, while there are other sectors where frantic activity is taking place among many objects (e.g. a space battle). This can lead to a highly unequal workload distribution among the nodes of the cluster. Also, this approach can be difficult to scale, unless the size of the simulated space is also expanded.
Even with very high computing power, it is still important for a simulation engine to adopt an efficient strategy for organizing and managing the simulated space and the simulated objects within the space. One common approach is to divide the simulated space into an “octree,” whereby cubes of simulated space are subdivided into groups of eight identical smaller cubes, at least some of which are subdivided into clusters of eight even smaller cubes, and so-forth. This approach is illustrated by FIG. 1, where a large cube 100 of simulated space is divided into eight smaller cubes 102 of equal dimensions. One of these eight cubes is then further divided into eight even smaller cubes 104.
Typically, a cube in the octree is subdivided only when the number of objects in the cube reaches a certain threshold, such as 100 objects in a given cube. For many of these simulations, the objects have finite sizes, and in some cases also specific shapes and orientations. Once the cube is subdivided, objects in the cube will be “dropped” into smaller sub-cubes, and thereby into the next lower level of the tree, only if they do not overlap any sub-cube boundaries. Objects that would overlap a boundary of a sub-cube are retained at the higher level of the tree.
In addition to sizes and shapes, simulated objects sometimes also have interaction radii, also called interaction spheres. For example, an object may be able to see other objects only if they are located within a specified visibility radius, also called a visibility “sphere.” FIG. 2 presents an example in two dimensions where a simulated asteroid 200 becomes visible to a simulated spaceship 202 only when it crosses within the visibility sphere 204 of the spaceship 202. This approach can be computationally efficient, but it can be problematic to realistically represent the visibility of objects of different sizes. For example, the large asteroid 200 in FIG. 2 may reasonably be visible to the spaceship 202 when it is at the visibility radius 204, however it may not be realistic to also make the much smaller asteroid 206 visible to the spaceship 202 even at a somewhat closer distance. Note that in many implementations, the interaction spheres are actually rectangular or cubical in shape.
An important task for a simulation engine is to determine in real time for each simulated object whether there are any other simulated objects located near enough to be visible or otherwise to trigger an interaction of some kind with that object. One approach is to review the locations of all of the objects to determine which if any of the objects is located within an interaction sphere of another object. However, for this approach the number of inter-object distance calculations that must be performed rises as the square of the number of objects. Hence, this approach can be impractical when simulating the interactions of a large number of objects
A more efficient approach for large numbers of simulated objects is to divide the task into at least two steps, as illustrated in FIG. 3. For each object 300 in the simulation, the first step is to determine which cubes in the octree are overlapped by the interaction sphere 302 for that object. Then in subsequent steps it is only necessary to consider the distances between the selected object 300 and whatever objects 304, 306 are located in the overlapped cubes.
For example, in the two-dimensional illustration of FIG. 3, which shows a rectangular portion of a larger space, the interaction sphere 302 for object 300 overlaps six squares, including the square inhabited by the selected object 300. Accordingly, objects 304, 306, 308 which are located in overlapped cubes need to be considered in more detail to determine if they are located within the interaction sphere 302 of the selected object 300. Some of them 308 may be “false positives” that are located within an overlapped square but are not located within the interaction sphere 302. Nevertheless, this approach reduces the total number of objects that need to be considered. In this example, objects 310 and 312 are located in non-overlapped spheres (or squares) and need not be considered. The result can be a much lower total number of object comparisons. However, the step of determining which spheres overlap which cubes can be computationally demanding, and can be difficult to support for very large simulations.
What is needed, therefore, is a highly scalable engine for simulating interactions between objects in a space, where the computing workload is efficiently parallelized, interacting objects are quickly and efficiently identified, and the visibility of objects of different sizes is realistically represented.